1900C - Anji's Binary Tree - CodeForces Solution

//@author: DroseUnbreakble
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 3e5 + 3;

int note[N];
string s;
pair <int, int> a[N];

int trace(int id) {

    if(a[id].fi == 0 && a[id].se == 0) return 0;

    int &ret = note[id];

    if(ret != -1) return ret;
    ret = 1e9;

    if(s[id] == 'U') {
        if(a[id].fi) ret = min(ret, trace(a[id].fi) + 1);
        if(a[id].se) ret = min(ret, trace(a[id].se) + 1);
    }

    if(s[id] == 'L') {
        if(a[id].fi) ret = min(ret, trace(a[id].fi));
        if(a[id].se) ret = min(ret, trace(a[id].se) + 1);
    }

    if(s[id] == 'R') {
        if(a[id].fi) ret = min(ret, trace(a[id].fi) + 1);
        if(a[id].se) ret = min(ret, trace(a[id].se));
    }

    return ret;
}

int32_t main(){
   cin.tie(0)->sync_with_stdio(0);
   if(fopen("sus.inp", "r")){
     freopen("sus.inp", "r", stdin);
     freopen("sus.out", "w", stdout);
   }

   int t;
   cin >> t;
   while(t--) {
      memset(note, -1, sizeof(note));
      int n;
      cin >> n;
      cin >> s; s = " " + s;
      for(int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se;

      int ans = trace(1);
      cout << ans << '\n';
   }
}